package week7th;

import week7th.jsjf.LinkedBinaryTree;

import java.util.Iterator;
import java.util.Stack;

public class infixToSuffix {
    public String  toSuffix(String infix) {
        String result = "";
        String[] array = infix.split("\\s+"); // 以String数组存储中缀表达式的每个数字、符号
        Stack<LinkedBinaryTree> num = new Stack(); // 数字栈
        Stack<LinkedBinaryTree> op = new Stack(); // 操作符栈

        for (int a = 0; a < array.length; a++) {
            if (array[a].equals("+") || array[a].equals("-") || array[a].equals("*") || array[a].equals("/")) {  // 判断数组中字符类型（数字or操作符），分别装入两个栈中
                if (op.empty()) {
                    op.push(new LinkedBinaryTree<>(array[a]));
                } else {
                    if ((op.peek().root.element).equals("+") || (op.peek().root.element).equals("-") && array[a].equals("*") || array[a].equals("/")) {
                        op.push(new LinkedBinaryTree(array[a]));  // 如果操作符栈中已经有“+、-”操作符而后来的的是“*、/”，压入op,若不是，进行树的构建，在压入op
                    } else {
                        LinkedBinaryTree right = num.pop();
                        LinkedBinaryTree left = num.pop();
                        LinkedBinaryTree temp = new LinkedBinaryTree(op.pop().root.element, left, right);
                        num.push(temp);
                        op.push(new LinkedBinaryTree(array[a]));
                    }
                }
            } else {
                num.push(new LinkedBinaryTree<>(array[a]));
            }
        }
        while (!op.empty()) {
            LinkedBinaryTree right = num.pop();
            LinkedBinaryTree left = num.pop();
            LinkedBinaryTree temp = new LinkedBinaryTree(op.pop().root.element, left, right);
            num.push(temp);
        }

        Iterator itr = num.pop().iteratorPostOrder();
        while (itr.hasNext()){
            result += itr.next()+" ";
        }

        return result;
    }

}
